

<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 9, Exercise 15<BR>

<BR>

</H1>



Exercise 9 suggests an improvement to the

<code class=code>DeleteMax</code> function given in the text,

and Exercise 10 suggests the use of two elements

<code class=code>MinElement</code>

and

<code class=code>MaxElement</code>

to reduce the total number of comparisons being

performed.

Combining these ideas results in the

<code class=code>MaxHeap</code> code given below

and in the file

<code class=var>maxheap6.h</code>.





<HR class = coderule>

<pre class = code>

template&lt;class T&gt;

class MaxHeap {

   public:

      MaxHeap(int MaxHeapSize, T maxElement,

              T minElement);

      ~MaxHeap() {delete [] heap;}

      int Size() const {return CurrentSize;}

      T Max() {if (CurrentSize == 0)

                  throw OutOfBounds();

               return heap[1];}

      MaxHeap&lt;T&gt;&amp; Insert(const T&amp; x);

      MaxHeap&lt;T&gt;&amp; DeleteMax(T&amp; x);

      void Initialize(T a[], int size, int ArraySize,

           int minElement, int maxElement);

      void Deactivate() {heap = 0;}

   private:

      int CurrentSize,

          MaxSize;

      T MaxElement,  // all must be &lt;= MaxElement

        MinElement;  // all must be &gt;= MinElement

      T *heap;  // element array

};



template&lt;class T&gt;

MaxHeap&lt;T&gt;::MaxHeap(int MaxHeapSize,

            T maxElement, T minElement)

{// Max heap constructor.

   MaxSize = MaxHeapSize;

   MaxElement = maxElement;

   MinElement = minElement;

   heap = new T[2*(MaxSize+1)];



   // put MaxElement in heap[0]

   heap[0] = MaxElement;



   // put MinElement in all other positions

   for (int i = 1; i &lt;= 2*MaxSize + 1; i++)

      heap[i] = MinElement;



   CurrentSize = 0;

}



template&lt;class T&gt;

MaxHeap&lt;T&gt;&amp; MaxHeap&lt;T&gt;::Insert(const T&amp; x)

{// Insert x into the max heap.

   if (CurrentSize == MaxSize)

      throw NoMem(); // no space

   if (x &lt; MinElement || x &gt; MaxElement)

      throw BadInput();



   // find place for x

   // i starts at new leaf and moves up tree

   int i = ++CurrentSize;

  

   // no need to check if root reached

   // because heap[0] = MaxElement

   while (x &gt; heap[i/2]) {

      // cannot put x in heap[i]

      heap[i] = heap[i/2]; // move element down

      i /= 2;              // move to parent

      }



   heap[i] = x;

   return *this;

}



template&lt;class T&gt;

MaxHeap&lt;T&gt;&amp; MaxHeap&lt;T&gt;::DeleteMax(T&amp; x)

{// Set x to max element and delete

 // max element from heap.

   // check if heap is empty

   if (CurrentSize == 0)

      throw OutOfBounds(); // empty



   x = heap[1]; // max element



   // restructure heap

   T y = heap[CurrentSize]; // last element

   // replace with MinElement

   heap[CurrentSize--] = MinElement;



   // first propagate vacancy to a leaf

   int i = 1,  // current node of heap

       ci = 2; // child of i

   while (ci &lt;= CurrentSize) {

      // heap[ci] should be larger child of i

      // no need to check if ci &lt; CurrentSize

      // because heap[CurrentSize] has MinElement

      if (heap[ci] &lt; heap[ci+1]) ci++;



      // move larger child to heap[i]

      heap[i] = heap[ci]; // move child up

      i = ci;             // move down a level

      ci *= 2;

      }



   i = ci/2;

   // vacancy at heap[i], start from here

   // and insert y

   // no need to check if root reached

   // because heap[0] = MaxElement

   while (y &gt; heap[i/2]) {

      // cannot put y in heap[i]

      heap[i] = heap[i/2]; // move element down

      i /= 2;              // move to parent

      }



   heap[i] = y;



   return *this;

}



template&lt;class T&gt;

void MaxHeap&lt;T&gt;::Initialize(T a[], int size,

                 int ArraySize, int minElement, int maxElement)

{// Initialize max heap to array a[0:ArraySize].

   if (ArraySize &lt; 2*size + 1)

      throw BadInput();  // not enough space for

                         // MinElement children of

                         // leaves

   // set private data members of MaxHeap

   delete [] heap;

   heap = a;

   CurrentSize = size;

   MaxElement = maxElement;

   MinElement = minElement;

   heap[0] = MaxElement;

   // fill rest of array with MinElement

   for (int i = size + 1; i &lt;= ArraySize; i++)

      heap[i] = MinElement;

   MaxSize = (ArraySize - 1)/2;



   // make into a max heap

   // by running old method as we do not

   // expect to propagate all the way down

   for (int i = CurrentSize/2; i &gt;= 1; i--) {

      T y = heap[i]; // root of subtree



      // find place to put y

      int c = 2*i; // parent of c is target

                   // location for y

      while (c &lt;= CurrentSize) {

         // heap[c] should be larger sibling

         // no need to check if c &lt; CurrentSize as

         // all unused spots have MinElement

         if (heap[c] &lt; heap[c+1]) c++;



         // can we put y in heap[c/2]?

         if (y &gt;= heap[c]) break;  // yes



         // no

         heap[c/2] = heap[c]; // move child up

         c *= 2; // move down a level

         }

      heap[c/2] = y;

      }

}

<hr class=coderule>

</pre>

<br><br>

We must also change the code for the heap sort function so that

it conforms to the requirements of the changed

<code class=code>Initialize</code>

function.  This requires us to define <code class=code>MinElement</code>

and

<code class=code>MaxElement</code>.

The new code is given below and in the file

<code class=code>hsort2.h</code>.





<HR class = coderule>

<pre class = code>

template &lt;class T&gt;

void HeapSort(T a[], int n)

{// Sort a using the heap sort method.

 // Elements are in a[1:n] and array has

 // positions a[0:2n + 1].

   if (n &lt; 2) return;

   // first find min and max elements

   T Min = a[1];

   for (int i = 2; i &lt;= n; i++)

      if (Min &gt; a[i]) Min = a[i];



   T Max = a[1];

   for (int i = 2; i &lt;= n; i++)

      if (Max &lt; a[i]) Max = a[i];



   // create a max heap of the elements

   MaxHeap&lt;T&gt; H(1,0,1);

   H.Initialize(a,n,2*n+1,Min,Max);



   // extract one by one from the max heap

   T x;

   for (int i = n-1; i &gt;= 1; i--) {

      H.DeleteMax(x);

      a[i+1] = x;

      }



   // save array a from heap destructor

   H.Deactivate();

}

<hr class=coderule>

</pre>



</FONT>

</BODY>

</HTML>

